package a4_p04_jw_kw.euler;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.Pseudograph;

import a1_p04_jw_kw.graph.GraphCreater;
import a1_p04_jw_kw.graph.GraphParser;
import a1_p04_jw_kw.struct.GraphStatistic;
import a1_p04_jw_kw.struct.Node;
import a4_p04_jw_kw.searchalgo.HolzerDFS;

public class Hierholzer {
    Graph<Node, DefaultWeightedEdge> testGraph;
    Graph<Node, DefaultWeightedEdge> g;
    ArrayList<Node> eulerCycle;
    Graph<Node, DefaultWeightedEdge> subGraph;

    GraphStatistic stats = new GraphStatistic();

    long clock;

    public Hierholzer() {
    }

    public void createEulerTour(String start, Graph<Node, DefaultWeightedEdge> g) {

        this.g = g;

        // System.out.println("clone graphen");
        subGraph = cloneGraph(g);
        // System.out.println("subGraph: " + subGraph);
        // System.out.println("origraph: " + g);
        // System.out.println("gCopy.equals(g): " + gCopy.equals(g));

        ArrayList<Node> cycle = new ArrayList<Node>();
        HolzerDFS dfs = new HolzerDFS(g);

        startWatch();

//        System.out.println("starte erste dfs suche");
        dfs.startSearch(start);
        cycle = dfs.getWay();
//        System.out.println("cycle: " + cycle);

        Set<DefaultWeightedEdge> cycleEdges = getEdgesOfCycle(cycle);
        Set<DefaultWeightedEdge> removeEdges = cycleEdges;

        // 2. Wenn K ein Eulerkreis ist, breche ab, ansonsten:

        int x = 0;
//        System.out.println("pr�fe, ob eulerkreis");
        //while (!isEulerCycle(cycleEdges, g) && x < 5) {
        while (!isEulerCycle(cycleEdges, g)) {
            x++;
//            System.out.println("noch kein Eulerkreis");
            // 3. entferne alle Kanten von K aus G
//            System.out.println("entferne alle Kanten aus Cycle: " + cycleEdges);
            // subGraph.removeAllEdges(cycleEdges);
            // removeAllEdges(gCopy, removeEdges);
            // removeAllEdges(g, removeEdges);
            g.removeAllEdges(removeEdges);

            // 4. Suche Eckpunkt von K mit Kante gr��er 0 und kreiere neuen
            // Kreis K*

//            System.out.println("n�chster DFS Durchlauf");
            // HolzerDFS k1 = new HolzerDFS(gCopy);
            HolzerDFS k1 = new HolzerDFS(g);
            ArrayList<Node> k1List = new ArrayList<Node>();

            // Node n = findCornerNode(cycle, gCopy, removeEdges);
            // if (n == null) {
            // System.out.println("no neighbor corner found");
            // break;
            // }
            Node n = findCornerNode(cycle, g, removeEdges);
//            System.out.println("Starte K1 search");
            k1.startSearch(n.name);
            k1List = k1.getWay();
//            System.out.println("k1: " + k1List);

            // 5. F�ge K* an richtiger Stelle in K ein ( Eckpunkt = einf�gen des
            // K*)
//            System.out.println("cycle zusammenf�gen, cycle alt:" + cycle
//                    + "k1: " + k1List);
            cycle = insertK(cycle, k1List, n);
//            System.out.println("cycle neu: " + cycle);
            // 6. Nenne den so erhaltenen Kreis K (= cycle setzen) und Schritt 2
            cycleEdges = getEdgesOfCycle(cycle);
//            System.out.println("neue Edgeliste: " + cycleEdges);
            removeEdges = getEdgesOfCycle(k1List);
//            System.out.println("removeEdges: " + removeEdges);
        }

        eulerCycle = cycle;

        stopWatch();
        // System.out.println(cycleEdges);

    }

    private void removeAllEdges(Graph<Node, DefaultWeightedEdge> subGraph,
            Set<DefaultWeightedEdge> removeEdges) {
        for (DefaultWeightedEdge edge : removeEdges) {
            subGraph.removeEdge(edge);
        }

    }

    private ArrayList<Node> insertK(ArrayList<Node> cycle,
            ArrayList<Node> k1List, Node n) {

        ArrayList<Node> result = new ArrayList<Node>();

        int index = cycle.indexOf(n);

        for (int i = 0; i < index; i++) {
            result.add(cycle.get(i));
        }

        for (int j = 0; j < k1List.size() - 1; j++) {
            result.add(k1List.get(j));
        }

        for (int k = index; k <= cycle.size() - 1; k++) {
            result.add(cycle.get(k));
        }

        return result;
    }

    private Node findCornerNode(ArrayList<Node> cycle,
            Graph<Node, DefaultWeightedEdge> subGraph,
            Set<DefaultWeightedEdge> removeEdges) {

        HashMap<Node, Integer> countList = new HashMap<Node, Integer>();

        Set<DefaultWeightedEdge> subEdgeSet = subGraph.edgeSet();

        // ArrayList<Node> odds = new ArrayList<Node>();

//        System.out.println("eigentlich ver�nderter Subgraph");
//        System.out.println("subGraph: " + subGraph);

        // for (Node n : cycle) {
        // int neighbors = Graphs.neighborListOf(subGraph, n).size();
        // if (neighbors > 0) {
        // odds.add(n);
        // }
        // }
        //
        // if (!odds.isEmpty()) {
        // return odds.get(0);
        // } else {
        // System.out.println("no corner found in graph");
        // return null;
        // }
        // init countList
        for (Node n : cycle) {
            countList.put(n, 0);
        }

        // alle Kanten hochz�hlen
        for (DefaultWeightedEdge edge : subEdgeSet) {
            Node start = subGraph.getEdgeSource(edge);
            if (countList.containsKey(start)) {
                Integer sValue = countList.get(start);
                countList.put(start, (sValue + 1));
            }

            Node end = subGraph.getEdgeTarget(edge);
            if (countList.containsKey(end)) {
                Integer eValue = countList.get(end);
                countList.put(end, (eValue + 1));
            }
        }

        // gel�schte Kanten abziehen

        for (DefaultWeightedEdge e : removeEdges) {
            Node start = subGraph.getEdgeSource(e);
            if (countList.containsKey(start)) {
                Integer sValue = countList.get(start);
                countList.put(start, (sValue - 1));
            }

            Node end = subGraph.getEdgeTarget(e);
            if (countList.containsKey(end)) {
                Integer eValue = countList.get(end);
                countList.put(end, (eValue - 1));
            }
        }

//        System.out.println("countList:");
//        for (Node n : countList.keySet()) {
//            System.out.println("key: " + n + " value: " + countList.get(n));
//        }

        for (Node n : countList.keySet()) {
            if (countList.get(n) > 0 && cycle.contains(n)) {
                return n;
            }
        }

        return null;
    }

    private Graph<Node, DefaultWeightedEdge> cloneGraph(
            Graph<Node, DefaultWeightedEdge> g) {

        Pseudograph<Node, DefaultWeightedEdge> tmp = (Pseudograph<Node, DefaultWeightedEdge>) new Pseudograph<Node, DefaultWeightedEdge>(
                DefaultWeightedEdge.class);

        Set<Node> vertexSet = g.vertexSet();
        for (Node node : vertexSet) {
            tmp.addVertex(node);
        }

        Set<DefaultWeightedEdge> edgeSet = g.edgeSet();
        for (DefaultWeightedEdge e : edgeSet) {
            tmp.addEdge(g.getEdgeSource(e), g.getEdgeTarget(e));
        }

        return tmp;
    }

    private Set<DefaultWeightedEdge> getEdgesOfCycle(ArrayList<Node> cycle) {
        Set<DefaultWeightedEdge> edges = new HashSet<DefaultWeightedEdge>();
        for (int i = 0; i < cycle.size() - 1; i++) {
            edges.add(g.getEdge(cycle.get(i), cycle.get(i + 1)));
        }
        return edges;
    }

    public ArrayList<DefaultWeightedEdge> getEulerTour() {
        ArrayList<DefaultWeightedEdge> edges = new ArrayList<DefaultWeightedEdge>();
        for (int i = 0; i < this.eulerCycle.size() - 1; i++) {
            edges.add(subGraph.getEdge(this.eulerCycle.get(i), this.eulerCycle.get(i + 1)));
        }
        return edges;
    }

    private boolean isEulerCycle(Set<DefaultWeightedEdge> edges,
            Graph<Node, DefaultWeightedEdge> g) {

        Set<DefaultWeightedEdge> edgeSet = g.edgeSet();

        for (DefaultWeightedEdge e : edgeSet) {
            if (!edges.contains(e)) {
                return false;
            }
        }

        return true;
    }

    public Graph<Node, DefaultWeightedEdge> createHolzerGKA() {
        GraphParser gp = new GraphParser("hierholzer.gka");

        // create the graph as JGraphT graph
        GraphCreater gc = new GraphCreater(gp.getGraphSetup());
        gc.createGraph();
        return gc.getGraph();
    }

    public GraphStatistic getStatistic() {
        return this.stats;

    }

    private void startWatch() {
        this.clock = System.currentTimeMillis();

    }

    private void stopWatch() {
        long stop = System.currentTimeMillis();
        stats.time = stats.time + (stop - clock);

    }

	public ArrayList<Node> getEulerCycle() {
		return eulerCycle;
	}

}
